//剑指offer63 数据流中的中位数


//思路
//建立一个大根堆和小根堆
//大根堆用来存放小数据，小根堆用来存放大数据  这样如果是奇数个，中位数就为high.peek(),如果是偶数，中位数就为(high.peek()+low.peek())/2

import java.util.PriorityQueue;
import java.util.Comparator;
public class Solution{
	private int count=0;//记录存入的个数
	private PriorityQueue<Integer> low=new PriorityQueue<>();//小根堆，用来存放大数据
	private PriorityQueue<Integer> high=new PriorityQueue<>(new Comparator<Integer>(){
		@Override
		public int compare(Integer o1,Integer o2){
			return o2.compareTo(o1);
		}
	});//重写compare方法，使high成为大根堆，用来存放小数据
	public void Insert(Integer num){
		count++;
		if((count&1)==1){//为奇数个
			if(!low.isEmpty()&&num>low.peek()){//说明num更大，应该放入low中,再将low中最小元素放入high中
				low.offer(num);
				num=low.poll();
			}
			high.offer(num);
		}
		else{
			if(!high.isEmpty()&&num<high.peek()){//说明num更小，应该放入high中,再将high中最小元素放入low中
				high.offer(num);
				num=high.peek();
			}
			low.offer(num);
		}
	}
	//每放入到low或者high中一个元素，就往high或者low中再补上一个low.poll()或者high.poll(),这样做的目的是为了让low和high的容量相等或者之差为1，方便计算中位数
	
	public Double GetMedian(){
		double tmp=0;
		if((count&1)==1){
			tmp=high.peek();
		}else{
			tmp=(high.peek()+low.peek())/2;
		}
	return tmp;
	}
}